package com.zwj.interview.动态规划.背包问题;

/**
 * @Author: Zwj
 * @Date: 2022/2/26 17:34
 * 给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。
 * <p>
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：nums 可以分割成 [1, 5, 5] 和 [11]
 */
public class 分割等和子集 {

    /**
     * 这是一个典型的0-1背包问题，假设数组所有的元素的和为sum，那么就是求出能不能有两个和为sum/2的子集，转化为背包问题就是：
     * <p>
     * 给一个可装载质量为sum/2的背包和N个物品，每个物品的重量为nums[i]，现在让你装物品，是否存在一种方法，能够恰好将背包装满
     * <p>
     * 我们这里定义dp[i][j]=x表示，对于前i个物品，当前背包的容量为j时，若x为true，则可以恰好将背包装满，若x为false，则说明不能将
     * 背包装满
     *
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum = sum / 2;
        boolean[][] dp = new boolean[n + 1][sum + 1];
        //base case
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        /**
         * 如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序:
         * for num in nums:
         *     for i in range(target, num-1, -1):
         */
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                //如果背包容量不足，肯定不能将第i个物品放入
                if (j - nums[i - 1] < 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    /**
                     * dp[i - 1][j]表示不放入第i个物品
                     * dp[i - 1][j - nums[i - 1]]表示将第i个物品放入
                     */
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][sum];
    }



}